/*
 * @lc app=leetcode.cn id=650 lang=typescript
 *
 * [650] 只有两个键的键盘
 */

// @lc code=start
function minSteps(n: number): number {
  // dp[i][j]，记事本上i个字符，粘贴板上j个字符的最小操作次数
  const dp = new Array(n + 1).fill(0).map((_) => new Array(n + 1).fill(1001));
  // 初始化
  dp[1][0] = 0;
  dp[1][1] = 1;
  // 验证i到n的过程
  for (let i = 2; i <= n; i++) {
    let min = 1001;
    for (let j = 0; j <= (i / 2) >> 0; j++) {
      // 最后一次操作是paste
      dp[i][j] = dp[i - j][j] + 1;
      min = Math.min(min, dp[i][j]);
    }
    // 最后一次操作是copy，i必然等于j
    dp[i][i] = min + 1;
  }

  return Math.min(...dp[n]);
}
// @lc code=end
